﻿using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using DsLib;

namespace TestCode
{
    public static class TestBST
    {
        #region StringBSTTests
        public static void TestStringBST()
        {
            BinarySearchTree<string> _tree = new BinarySearchTree<string>();

            int[] arr = { 1, 2, 3, 1, 4, 5, 2, 3, 6, 4, 8, 9, 10, 11, 34, 12, 11, 0, 6, 9, 6, 1, 1, 1, 4, 3, 6, 2, 1, 24, 5, 3, 6 };

            //int[] arr = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };

            List<string> strArr = new List<string>(arr.Length);

            foreach (int i in arr)
            {
                strArr.Add(i.ToString());
            }
            foreach (int i in arr)
            {
                _tree.Add(i.ToString());
            }

            Console.WriteLine("Count: " + _tree.Count);

            Array.Sort(arr);

            foreach (int i in arr)
            {
                _tree.PrintValueStatusInBST( i.ToString());
            }

            _tree.Remove("11");
            Console.WriteLine("Count: " + _tree.Count);

            _tree.PrintValueStatusInBST( "11");

            _tree.Remove("11");

            Console.WriteLine("Count: " + _tree.Count);

            _tree.PrintValueStatusInBST( "11");

            _tree.PrintValueStatusInBST( "50");

            _tree.Add("50");
            Console.WriteLine("Count: " + _tree.Count);

            _tree.PrintValueStatusInBST( "50");

            _tree.Remove("51");

            Console.WriteLine("Count: " + _tree.Count);

            int count = 0;
            foreach (int i in arr)
            {
                Console.WriteLine(string.Format("Deleting {0} at {1}", i, count++));
                _tree.Remove(i.ToString());
            }

            Console.WriteLine("Count: " + _tree.Count);

            _tree.Remove("50");

            Console.WriteLine("Count: " + _tree.Count);

            _tree.Add("50");

            Console.WriteLine("Count: " + _tree.Count);
        }

        public static void TestStringBST2()
        {
            string filePath = @"..\..\Resources\eng_words.txt";
            if (File.Exists(filePath))
            {
                string[] arr = File.ReadAllLines(filePath);
                BinarySearchTree<string> _tree = new BinarySearchTree<string>();

                // Randomize the input
                Random rand = new Random();
                for (int i = 0; i < arr.Length; i++)
                {
                    int randNum = rand.Next(0, arr.Length - 1);

                    string s = arr[i];
                    arr[i] = arr[randNum];
                    arr[randNum] = s;
                }

                // Add to tree
                foreach (string s in arr)
                {
                    _tree.Add(s);
                }

                // Do Search
                _tree.PrintValueStatusInBST("munish");
                _tree.PrintValueStatusInBST("zoom");
                _tree.PrintValueStatusInBST("mute");
                _tree.PrintValueStatusInBST("rouse");
                _tree.PrintValueStatusInBST("zulusi");
                
                // Do traversals
                string traversal;
                Console.WriteLine("Inorder: ");
                _tree.Traverse(TreeTraversalType.InOrder, true, out traversal);

                Console.WriteLine("Preorder: ");
                _tree.Traverse(TreeTraversalType.PreOrder, true, out traversal);

                Console.WriteLine("Postorder: ");
                _tree.Traverse(TreeTraversalType.PostOrder, true, out traversal);
            }
        }

        public static void TestStringBST3()
        {
            string filePath = @"..\..\Resources\eng_words.txt";
            if (File.Exists(filePath))
            {
                string[] arr = File.ReadAllLines(filePath);
                BinarySearchTree<EnglishDictionaryWord> _tree = new BinarySearchTree<EnglishDictionaryWord>(new WordLengthComparer());
                //BinarySearchTree<string> _tree = new BinarySearchTree<string>();

                // Randomize the input
                Random rand = new Random();
                for (int i = 0; i < arr.Length; i++)
                {
                    int randNum = rand.Next(0, arr.Length - 1);

                    string s = arr[i];
                    arr[i] = arr[randNum];
                    arr[randNum] = s;
                }

                // Add to tree
                foreach (string s in arr)
                {
                    _tree.Add(new EnglishDictionaryWord(s, WordCompareType.Lexical));
                }

                // Do Search
                _tree.PrintValueStatusInBST(new EnglishDictionaryWord("munish", WordCompareType.Length));
                _tree.PrintValueStatusInBST(new EnglishDictionaryWord("zoom", WordCompareType.Length));
                _tree.PrintValueStatusInBST(new EnglishDictionaryWord("mute", WordCompareType.Length));
                _tree.PrintValueStatusInBST(new EnglishDictionaryWord("rouse", WordCompareType.Length));
                _tree.PrintValueStatusInBST(new EnglishDictionaryWord("zulusi", WordCompareType.Length));

                // Do traversals
                string traversal;
                Console.WriteLine("Inorder: ");
                _tree.Traverse(TreeTraversalType.InOrder, true, out traversal);

                Console.WriteLine("Preorder: ");
                _tree.Traverse(TreeTraversalType.PreOrder, true, out traversal);

                Console.WriteLine("Postorder: ");
                _tree.Traverse(TreeTraversalType.PostOrder, true, out traversal);
            }
        }

        #endregion

        #region IntBSTTests
        public static void TestIntBST()
        {
            BinarySearchTree<int> _tree = new BinarySearchTree<int>();

            int[] origArr = { 1, 2, 3, 1, 4, 5, 2, 3, 6, 4, 8, 9, 10, 11, 34, 12, 11, 0, 6, 9, 6, 1, 1, 1, 4, 3, 6, 2, 1, 24, 5, 3, 6 };

            //int[] arr = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };

            // Add to tree
            foreach (int i in origArr)
            {
                _tree.Add(i);
            }

            Console.WriteLine("Count: " + _tree.Count);

            int[] arr = new int[origArr.Length];

            // create array copy
            Array.Copy(origArr, arr, origArr.Length);

            // search values in tree (input is now sorted array)
            Array.Sort(arr);

            foreach (int i in arr)
            {
                _tree.PrintValueStatusInBST(i);
            }

            _tree.Remove(11);
            Console.WriteLine("Count: " + _tree.Count);
            _tree.PrintValueStatusInBST(11);
            _tree.Remove(11);
            Console.WriteLine("Count: " + _tree.Count);
            _tree.PrintValueStatusInBST(11);

            _tree.PrintValueStatusInBST(50);

            _tree.Add(50);
            Console.WriteLine("Count: " + _tree.Count);

            _tree.PrintValueStatusInBST(50);

            _tree.Remove(51);
            Console.WriteLine("Count: " + _tree.Count);

            // delete all
            int count = 0;
            foreach (int i in arr)
            {
                Console.WriteLine(string.Format("Deleting {0} at {1}", i, count++));
                _tree.Remove(i);
            }

            Console.WriteLine("Count: " + _tree.Count);

            // add all again
            foreach (int i in origArr)
            {
                _tree.Add(i);
            }

            // do traversals
            string traversal;
            Console.WriteLine("Inorder: ");
            _tree.Traverse(TreeTraversalType.InOrder, true, out traversal);

            Console.WriteLine("Preorder: ");
            _tree.Traverse(TreeTraversalType.PreOrder, true, out traversal);

            Console.WriteLine("Postorder: ");
            _tree.Traverse(TreeTraversalType.PostOrder, true, out traversal);
        }

        #endregion

        #region EnumeratorTests
        public static void TestBSTCollection()
        {
            BinarySearchTree<int> _tree = new BinarySearchTree<int>();

            int[] origArr = { 1, 2, 3, 1, 4, 5, 2, 3, 6, 4, 8, 9, 10, 11, 34, 12, 11, 0, 6, 9, 6, 1, 1, 1, 4, 3, 6, 2, 1, 24, 5, 3, 6 };

            //int[] arr = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };

            // Add to tree
            foreach (int i in origArr)
            {
                _tree.Add(i);
            }

            // get enumerator
            foreach (var n in _tree)
            {
                Console.WriteLine(n.ToString());
            }

            int[] array = new int[origArr.Length];
            _tree.CopyTo(array, 0);

            // print out array
            foreach (var n in array)
            {
                Console.WriteLine(n.ToString());
            }
        }

        public static void TestCollectionEnumerator()
        {
            BinarySearchTree<int> _tree = new BinarySearchTree<int>();

            int[] origArr = { 1, 2, 3, 1, 4, 5, 2, 3, 6, 4, 8, 9, 10, 11, 34, 12, 11, 0, 6, 9, 6, 1, 1, 1, 4, 3, 6, 2, 1, 24, 5, 3, 6 };

            //int[] arr = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };

            // Add to tree
            foreach (int i in origArr)
            {
                _tree.Add(i);
            }

            // Indexer test
            for (int i = 0; i < _tree.Count; i++)
            {
                Console.WriteLine("At " + i + " found " + _tree[i].ToString());
            }

            int count = 0;

            try
            {
                // get enumerator
                foreach (var n in _tree)
                {
                    Console.WriteLine(n.ToString());

                    //if (count++ == 20)
                    //    _tree.Add(15);
                }
            }
            catch
            {

            }

        }
        #endregion
    }
}
